package com.scott.ch400.atguigu.ch034.stack;

/**
 * @author 黄后林
 * @date 2022-08-15 05:39:53
 * @note 且行且珍惜
 */
public class Calculator {

    public static void main(String[] args) {

        Calculator calculator= new Calculator();
        String exp="7+3*6/2-2*5";
        calculator.cal( exp);

    }

    public int cal(String exp){

        // String exp="2+3*6-2*5";

        //1、创建 数栈
        ArrayStack numStack = new ArrayStack(10);
        //2、创建 运算符栈
        ArrayStack operationStack = new ArrayStack(10);

        //3、定义各种变量
        int index=0;  //字符串exp从下标0开始扫描

        int num1=-1;  //第1个从数栈中出栈的数
        int num2=-1;  //第2个从数栈中出栈的数

        // operation 保存运算符
        int operation=' ';
        int rs =-1; //最终结果

        char ch= ' '; //将每次扫描到的字符保存到ch中

        //4 主要逻辑

        // 第1个循环
        while(true){

           //只有1个字符的字符串
           ch = exp.substring(index, index + 1).charAt(0);
           if(operationStack.isOperation(ch)){
               //如果ch是运算符
               if(!operationStack.isEmpty()){

                   //符号栈有运算符

                   //当前的操作符的优先级
                   int cur =operationStack.priority(ch);

                   //栈顶的操作符的优先级
                   int peek = operationStack.priority(operationStack.peek());

                   if(cur <= peek){

                       //            1、从数栈中取出2个数                 【 出栈 】
                       num1 = numStack.pop();
                       num2 = numStack.pop();

                       //            2、从符号栈中取出1个符号              【 出栈 】
                       operation = operationStack.pop();

                       //            3、进行运算
                       rs = numStack.cal(num1,num2,operation);

                       //            4、将运算的结果入数栈。               【 入栈 】
                       numStack.push(rs);

                       //            5、把当前操作符入符号栈。             【 入栈 】
                       operationStack.push(ch);

                   }else{
                       // cur > peek  当前操作符比栈顶的元素的优先级高
                       operationStack.push(ch);
                   }

               }else{
                   // 符号栈为空
                   operationStack.push(ch);
               }

           }else{
               //如果ch是数字  '1' 比 1  大48
               numStack.push(ch - 48);
           }

           //index往前走1个
           index = index+1;

           if(index == exp.length()){

               //整个字符串扫描完毕
               break;

           }

        }

        // 当表达式扫描完毕、就顺序从数栈和符号栈中pop出相应的数字和符号，并进行运算。
        // 第2个循环
        while(true){
            if(operationStack.isEmpty()){
                //如果运算符栈为空 则得到了最后的结果 保存在数栈中
                break;
            }

            //            1、从数栈中取出2个数                 【 出栈 】
            num1 = numStack.pop();
            num2 = numStack.pop();

            //            2、从符号栈中取出1个符号              【 出栈 】
            operation = operationStack.pop();

            //            3、进行运算
            rs = numStack.cal(num1,num2,operation);

            //            4、将运算的结果入数栈。               【 入栈 】
            numStack.push(rs);

        }
        rs =numStack.pop();
        System.out.printf("表达式 %s = %d",exp,rs);


        return rs;

    }
}

//1 创建1个基于数组的栈
class ArrayStack{

    private int maxSize; //栈的大小 最多可以放多少个元素
    private int[] stack; //栈中的数据存放在stack数组中、使用数组模拟栈

    //top表示栈顶，初始化为-1，表示没有数据
    //因为数组的下标从0开始 当top等于0的时候表示栈中有1个元素 top=1表示有2个元素
    private int top =-1;

    //初始化栈的大小
    public ArrayStack(int maxSize) {
        this.maxSize = maxSize;
        stack = new int[10];
    }



    //栈满
    public boolean isFull(){
        if(top == maxSize-1){
            return true;
        }
        return false;
    }

    //栈空
    public boolean isEmpty(){
        if(top == -1){
            return true;
        }
        return false;
    }

    //入栈-push
    public void push(int data){
        if(isFull()){
            System.out.println("栈满...");
            return;
        }

        //入栈的关键代码
        top=top+1;
        stack[top]=data;

        System.out.println("入栈成功...");

    }

    //出栈-pop 将栈顶的数据返回、同时删除栈顶元素
    public int pop(){
        if(isEmpty()){
            // 不返回但抛出运行时异常 抛出异常的同时带有return的功能=结束方法的运行
            throw new RuntimeException("...栈空... ");
        }

        //出栈的关键代码

        //定义一个临时变量保存栈顶的值
        int data = stack[top];

        //栈顶指针往下移动1位
        top=top-1;

        return data;

    }

    // 偷看1眼栈顶的元素  peek = 偷看=窥视
    public int peek(){
        int data =stack[top];
        return data;
    }

    //打印栈
    public void printStack(){
        if(isEmpty()){
            System.out.println("栈空... 没有数据...");
            return;
        }

        // 遍历时、需要从栈顶开始显示数据 直到栈底
        for(int index=top; index>=0;index--){
            System.out.printf("stack[%d]=%d \n",index,stack[index]);
        }
    }

    // 返回运算符的优先级
    // 假设优先级用数字表示  且数字越大、优先级越好 [ 富贵用钱表示  钱越多 越富贵 ]
    public int priority(int operation){

        if(operation == '*' || operation == '/'){
            return 20;
        }else if (operation == '+' || operation == '-'){
            return 10;
        }else{
            // 假定当前的运算符只有 + - * /  不包含括号[小括号、中括号、大括号]
            // -1代表非法的输入
            return -1;
        }
    }

    // 当前的操作符是否是1个运算符
    public boolean isOperation(char operation){

        if(operation == '*' || operation == '/' || operation == '+' || operation == '-' ){
            return true;
        }
        return false;
    }

    //运算
    public int cal(int num1 , int num2, int operation){
        // 用来存放计算的结果
        int rs = 0;

        if(operation== '+'){
            rs = num2+num1;
        }else if(operation== '-'){
            // 注意顺序 先进后出
            rs = num2-num1;
        }else if(operation== '*'){
            rs = num2*num1;
        }else if(operation== '/'){
            rs = num2/num1;
        }else {
            // 非法输入
            rs =-1;
        }
        return rs;
    }

}
